#include "Heap.h"

void Swap(HeapDataType* pnum1, HeapDataType* pnum2) {
    HeapDataType temp = *pnum1;    *pnum1 = *pnum2;    *pnum2 = temp;
}

// 向下调整法: 左右子树都是堆
void AdjustDown(HeapDataType* array, int n, int root) {
    int parent = root;          // 先找出左右孩子中最小的那个
    int child = parent * 2 + 1; // 左孩子
    while(child < n) {          // 建小堆
        if(child + 1 < n) {
            child = (array[child + 1] < array[child]) ? child + 1 : child;
        }
        if(array[child] < array[parent]) { 
            Swap(&array[parent], &array[child]);
            parent = child;
            child = parent * 2 + 1;
        }
        else { break; }
    }
}

void AdjustUp(HeapDataType* array, int n, int child) {
    int parent = (child - 1) / 2;
    while(child > 0) {
        if(array[child] < array[parent]) {
            Swap(&array[child], &array[parent]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else { break; }
    }
}

void HeapInit(Heap* pheap, HeapDataType* origin, int n) {
    pheap->_heap = (HeapDataType*)malloc(sizeof(HeapDataType) * n);
    memcpy(pheap->_heap, origin, sizeof(HeapDataType) * n);
    pheap->_size = n;    pheap->_capacity = n;
    for(int i = (n - 1 - 1) / 2; i >= 0; --i) { // 构建堆
        // i 为各子树的根节点的位序
        AdjustDown(pheap->_heap, pheap->_size, i);
    }
}

void HeapSort(HeapDataType* array, int n) {
    for(int i = (n - 1 -1) / 2; i >= 0; --i) {
        AdjustDown(array, n, i);
    }   int end = n - 1;
    while(end > 0) {
        Swap(&array[0], &array[end]);
        AdjustDown(array, end, 0); // 再继续选次小的
        --end;
    }
}

void HeapPrint(HeapDataType* pheap, int size) {
    assert(pheap);    printf("(堆顶)");
    for(int i = 0; i < size; i++) {
        printf(" %d ",pheap[i]);
    }   printf("(堆底)\n");
}


void HeapDestory(Heap* pheap) {
    assert(pheap);    free(pheap->_heap);
    pheap->_heap = NULL;
    pheap->_size = pheap->_capacity = 0;
}

void HeapPush(Heap* pheap, HeapDataType value){ // 尾插 → 向上调整为堆
    assert(pheap);
    if(pheap->_size == pheap->_capacity) {
        pheap->_capacity *= 2;
        pheap->_heap = (HeapDataType*)realloc(pheap->_heap, sizeof(HeapDataType) * pheap->_capacity);
    }   pheap->_heap[(pheap->_size)++] = value;
    AdjustUp(pheap->_heap, pheap->_size, pheap->_size - 1);
}

void HeapPop(Heap* pheap) { // 头删
    assert(pheap);    assert(pheap->_size > 0);
    Swap(&pheap->_heap[0], &pheap->_heap[pheap->_size - 1]);
    (pheap->_size)--; // 堆底元素出堆
    AdjustDown(pheap->_heap, pheap->_size, 0);
}

HeapDataType HeapTop(Heap* pheap) {
    assert(pheap);    return pheap->_heap[0];
}